Search Results

Documents authored by Altmeyer, Sebastian

Document
Artifact
DOI: 10.4230/DARTS.9.1.4
From FMTV to WATERS: Lessons Learned from the First Verification Challenge at ECRTS (Artifact)

Authors: Sebastian Altmeyer, Étienne André, Silvano Dal Zilio, Loïc Fejoz, Michael González Harbour, Susanne Graf, J. Javier Gutiérrez, Rafik Henia, Didier Le Botlan, Giuseppe Lipari, Julio Medina, Nicolas Navet, Sophie Quinton, Juan M. Rivas, and Youcheng Sun

Published in: DARTS, Volume 9, Issue 1, Special Issue of the 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
We propose here solutions to the FMTV 2015 challenge of a distributed video processing system using four different formalisms, as well as the description of the challenge itself. This artifact contains several solutions to various subchallenges, and instructions and scripts to reproduce these results smoothly.
Cite as

Sebastian Altmeyer, Étienne André, Silvano Dal Zilio, Loïc Fejoz, Michael González Harbour, Susanne Graf, J. Javier Gutiérrez, Rafik Henia, Didier Le Botlan, Giuseppe Lipari, Julio Medina, Nicolas Navet, Sophie Quinton, Juan M. Rivas, and Youcheng Sun. From FMTV to WATERS: Lessons Learned from the First Verification Challenge at ECRTS (Artifact). In Special Issue of the 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Dagstuhl Artifacts Series (DARTS), Volume 9, Issue 1, pp. 4:1-4:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{altmeyer_et_al:DARTS.9.1.4,
  author =	{Altmeyer, Sebastian and Andr\'{e}, \'{E}tienne and Dal Zilio, Silvano and Fejoz, Lo\"{i}c and Harbour, Michael Gonz\'{a}lez and Graf, Susanne and Guti\'{e}rrez, J. Javier and Henia, Rafik and Le Botlan, Didier and Lipari, Giuseppe and Medina, Julio and Navet, Nicolas and Quinton, Sophie and Rivas, Juan M. and Sun, Youcheng},
  title =	{{From FMTV to WATERS: Lessons Learned from the First Verification Challenge at ECRTS (Artifact)}},
  pages =	{4:1--4:6},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2023},
  volume =	{9},
  number =	{1},
  editor =	{Altmeyer, Sebastian and Andr\'{e}, \'{E}tienne and Dal Zilio, Silvano and Fejoz, Lo\"{i}c and Harbour, Michael Gonz\'{a}lez and Graf, Susanne and Guti\'{e}rrez, J. Javier and Henia, Rafik and Le Botlan, Didier and Lipari, Giuseppe and Medina, Julio and Navet, Nicolas and Quinton, Sophie and Rivas, Juan M. and Sun, Youcheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.9.1.4},
  URN =		{urn:nbn:de:0030-drops-180257},
  doi =		{10.4230/DARTS.9.1.4},
  annote =	{Keywords: Verification challenge, industrial use case, end-to-end latency, real-time systems, response time analysis}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.ECRTS.2023.19
From FMTV to WATERS: Lessons Learned from the First Verification Challenge at ECRTS (Invited Paper)

Authors: Sebastian Altmeyer, Étienne André, Silvano Dal Zilio, Loïc Fejoz, Michael González Harbour, Susanne Graf, J. Javier Gutiérrez, Rafik Henia, Didier Le Botlan, Giuseppe Lipari, Julio Medina, Nicolas Navet, Sophie Quinton, Juan M. Rivas, and Youcheng Sun

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
We present here the main features and lessons learned from the first edition of what has now become the ECRTS industrial challenge, together with the final description of the challenge and a comparative overview of the proposed solutions. This verification challenge, proposed by Thales, was first discussed in 2014 as part of a dedicated workshop (FMTV, a satellite event of the FM 2014 conference), and solutions were discussed for the first time at the WATERS 2015 workshop. The use case for the verification challenge is an aerial video tracking system. A specificity of this system lies in the fact that periods are constant but known with a limited precision only. The first part of the challenge focuses on the video frame processing system. It consists in computing maximum values of the end-to-end latency of the frames sent by the camera to the display, for two different buffer sizes, and then the minimum duration between two consecutive frame losses. The second challenge is about computing end-to-end latencies on the tracking and camera control for two different values of jitter. Solutions based on five different tools - Fiacre/Tina, CPAL (simulation and analysis), IMITATOR, UPPAAL and MAST - were submitted for discussion at WATERS 2015. While none of these solutions provided a full answer to the challenge, a combination of several of them did allow to draw some conclusions.
Cite as

Sebastian Altmeyer, Étienne André, Silvano Dal Zilio, Loïc Fejoz, Michael González Harbour, Susanne Graf, J. Javier Gutiérrez, Rafik Henia, Didier Le Botlan, Giuseppe Lipari, Julio Medina, Nicolas Navet, Sophie Quinton, Juan M. Rivas, and Youcheng Sun. From FMTV to WATERS: Lessons Learned from the First Verification Challenge at ECRTS (Invited Paper). In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{altmeyer_et_al:LIPIcs.ECRTS.2023.19,
  author =	{Altmeyer, Sebastian and Andr\'{e}, \'{E}tienne and Dal Zilio, Silvano and Fejoz, Lo\"{i}c and Harbour, Michael Gonz\'{a}lez and Graf, Susanne and Guti\'{e}rrez, J. Javier and Henia, Rafik and Le Botlan, Didier and Lipari, Giuseppe and Medina, Julio and Navet, Nicolas and Quinton, Sophie and Rivas, Juan M. and Sun, Youcheng},
  title =	{{From FMTV to WATERS: Lessons Learned from the First Verification Challenge at ECRTS}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.19},
  URN =		{urn:nbn:de:0030-drops-180486},
  doi =		{10.4230/LIPIcs.ECRTS.2023.19},
  annote =	{Keywords: Verification challenge, industrial use case, end-to-end latency}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2020.5
Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning

Authors: Filip Marković, Jan Carlson, Sebastian Altmeyer, and Radu Dobrin

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract
Schedulability analyses for preemptive real-time systems need to take into account cache-related preemption delays (CRPD) caused by preemptions between the tasks. The estimation of the CRPD values must be sound, i.e. it must not be lower than the worst-case CRPD that may occur at runtime, but also should minimise the pessimism of estimation. The existing methods over-approximate the computed CRPD upper bounds by accounting for multiple preemption combinations which cannot occur simultaneously during runtime. This over-approximation may further lead to the over-approximation of the worst-case response times of the tasks, and therefore a false-negative estimation of the system’s schedulability. In this paper, we propose a more precise cache-aware response time analysis for sporadic real-time systems under fully-preemptive fixed priority scheduling. The evaluation shows a significant improvement over the existing state of the art approaches.
Cite as

Filip Marković, Jan Carlson, Sebastian Altmeyer, and Radu Dobrin. Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{markovic_et_al:LIPIcs.ECRTS.2020.5,
  author =	{Markovi\'{c}, Filip and Carlson, Jan and Altmeyer, Sebastian and Dobrin, Radu},
  title =	{{Improving the Accuracy of Cache-Aware Response Time Analysis Using Preemption Partitioning}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.5},
  URN =		{urn:nbn:de:0030-drops-123682},
  doi =		{10.4230/LIPIcs.ECRTS.2020.5},
  annote =	{Keywords: Real-time systems, Fixed-Priority Preemptive Scheduling, Preemption delay}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.WCET.2019
OASIcs, Volume 72, WCET'19, Complete Volume

Authors: Sebastian Altmeyer

Published in: OASIcs, Volume 72, 19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019)

Abstract
OASIcs, Volume 72, WCET'19, Complete Volume
Cite as

19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019). Open Access Series in Informatics (OASIcs), Volume 72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{altmeyer:OASIcs.WCET.2019,
  title =	{{OASIcs, Volume 72, WCET'19, Complete Volume}},
  booktitle =	{19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-118-4},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{72},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2019},
  URN =		{urn:nbn:de:0030-drops-108667},
  doi =		{10.4230/OASIcs.WCET.2019},
  annote =	{Keywords: Theory of computation, Program analysis, Computer systems organization, Real-time systems, Software and its engineering, Software performance;}
}
Document
Front Matter
DOI: 10.4230/DARTS.5.1.0
Front Matter - ECRTS 2019 Artifacts, Table of Contents, Preface, Artifact Evaluation Committee

Authors: Sophie Quinton, Sebastian Altmeyer, and Alessandro Papadopoulos

Published in: DARTS, Volume 5, Issue 1, Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
Front Matter - ECRTS 2019 Artifacts, Table of Contents, Preface, Artifact Evaluation Committee
Cite as

Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 1, pp. 0:i-0:ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{quinton_et_al:DARTS.5.1.0,
  author =	{Quinton, Sophie and Altmeyer, Sebastian and Papadopoulos, Alessandro},
  title =	{{Front Matter - ECRTS 2019 Artifacts, Table of Contents, Preface, Artifact Evaluation Committee}},
  pages =	{0:i--0:ix},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{1},
  editor =	{Quinton, Sophie and Altmeyer, Sebastian and Papadopoulos, Alessandro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.5.1.0},
  URN =		{urn:nbn:de:0030-drops-107282},
  doi =		{10.4230/DARTS.5.1.0},
  annote =	{Keywords: Front Matter - ECRTS 2019 Artifacts, Table of Contents, Preface, Artifact Evaluation Committee}
}
Document
Front Matter
DOI: 10.4230/OASIcs.WCET.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Sebastian Altmeyer

Published in: OASIcs, Volume 72, 19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019). Open Access Series in Informatics (OASIcs), Volume 72, pp. 0:i-0:ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{altmeyer:OASIcs.WCET.2019.0,
  author =	{Altmeyer, Sebastian},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019)},
  pages =	{0:i--0:ix},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-118-4},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{72},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2019.0},
  URN =		{urn:nbn:de:0030-drops-107650},
  doi =		{10.4230/OASIcs.WCET.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ECRTS.2018
LIPIcs, Volume 106, ECRTS'18, Complete Volume

Authors: Sebastian Altmeyer

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
LIPIcs, Volume 106, ECRTS'18, Complete Volume
Cite as

30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{altmeyer:LIPIcs.ECRTS.2018,
  title =	{{LIPIcs, Volume 106, ECRTS'18, Complete Volume}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018},
  URN =		{urn:nbn:de:0030-drops-92441},
  doi =		{10.4230/LIPIcs.ECRTS.2018},
  annote =	{Keywords: Computer systems organization, Real-time systems, Computer systems organization, Embedded and cyber-physical systems, Software and its engineering}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ECRTS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Sebastian Altmeyer

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{altmeyer:LIPIcs.ECRTS.2018.0,
  author =	{Altmeyer, Sebastian},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.0},
  URN =		{urn:nbn:de:0030-drops-89763},
  doi =		{10.4230/LIPIcs.ECRTS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.WCET.2016.2
TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research

Authors: Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener

Published in: OASIcs, Volume 55, 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016)

Abstract
Engineering related research, such as research on worst-case execution time, uses experimentation to evaluate ideas. For these experiments we need example programs. Furthermore, to make the research experimentation repeatable those programs shall be made publicly available. We collected open-source programs, adapted them to a common coding style, and provide the collection in open-source. The benchmark collection is called TACLeBench and is available from GitHub in version 1.9 at the publication date of this paper. One of the main features of TACLeBench is that all programs are self-contained without any dependencies on standard libraries or an operating system.
Cite as

Heiko Falk, Sebastian Altmeyer, Peter Hellinckx, Björn Lisper, Wolfgang Puffitsch, Christine Rochange, Martin Schoeberl, Rasmus Bo Sørensen, Peter Wägemann, and Simon Wegener. TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research. In 16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016). Open Access Series in Informatics (OASIcs), Volume 55, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{falk_et_al:OASIcs.WCET.2016.2,
  author =	{Falk, Heiko and Altmeyer, Sebastian and Hellinckx, Peter and Lisper, Bj\"{o}rn and Puffitsch, Wolfgang and Rochange, Christine and Schoeberl, Martin and S{\o}rensen, Rasmus Bo and W\"{a}gemann, Peter and Wegener, Simon},
  title =	{{TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research}},
  booktitle =	{16th International Workshop on Worst-Case Execution Time Analysis (WCET 2016)},
  pages =	{2:1--2:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-025-5},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{55},
  editor =	{Schoeberl, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2016.2},
  URN =		{urn:nbn:de:0030-drops-68958},
  doi =		{10.4230/OASIcs.WCET.2016.2},
  annote =	{Keywords: Benchmark, WCET analysis, real-time systems}
}
Document
DOI: 10.4230/OASIcs.WCET.2015.65
WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?

Authors: Sebastian Altmeyer, Björn Lisper, Claire Maiza, Jan Reineke, and Christine Rochange

Published in: OASIcs, Volume 47, 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)

Abstract
Mixed-criticality systems integrate components of different criticality. Different criticality levels require different levels of confidence in the correct behavior of a component. One aspect of correctness is timing. Confidence in worst-case execution time (WCET) estimates depends on the process by which they have been obtained. A somewhat naive view is that static WCET analyses determines safe bounds in which we can have absolute confidence, while measurement-based approaches are inherently unreliable. In this paper, we refine this view by exploring sources of doubt in the correctness of both static and measurement-based WCET analysis.
Cite as

Sebastian Altmeyer, Björn Lisper, Claire Maiza, Jan Reineke, and Christine Rochange. WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 65-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{altmeyer_et_al:OASIcs.WCET.2015.65,
  author =	{Altmeyer, Sebastian and Lisper, Bj\"{o}rn and Maiza, Claire and Reineke, Jan and Rochange, Christine},
  title =	{{WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?}},
  booktitle =	{15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)},
  pages =	{65--74},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-95-8},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{47},
  editor =	{Cazorla, Francisco J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2015.65},
  URN =		{urn:nbn:de:0030-drops-52574},
  doi =		{10.4230/OASIcs.WCET.2015.65},
  annote =	{Keywords: mixed criticality, WCET analysis, confidence in WCET estimates}
}
Document
DOI: 10.4230/LITES-v001-i001-a001
A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays

Authors: Will Lunniss, Sebastian Altmeyer, and Robert I. Davis

Published in: LITES, Volume 1, Issue 1 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 1

Abstract
In multitasking real-time systems, the choice of scheduling algorithm is an important factor to ensure that response time requirements are met while maximising limited system resources. Two popular scheduling algorithms include fixed priority (FP) and earliest deadline first (EDF). While they have been studied in great detail before, they have not been compared when taking into account cache related pre-emption delays (CRPD). Memory and cache are split into a number of blocks containing instructions and data. During a pre-emption, cache blocks from the pre-empting task can evict those of the pre-empted task. When the pre-empted task is resumed, if it then has to re-load the evicted blocks, CRPD are introduced which then affect the schedulability of the task. In this paper we compare FP and EDF scheduling algorithms in the presence of CRPD using the state-of-the-art CRPD analysis. We find that when CRPD is accounted for, the performance gains offered by EDF over FP, while still notable, are diminished. Furthermore, we find that under scenarios that cause relatively high CRPD, task layout optimisation techniques can be applied to allow FP to schedule tasksets at a similar processor utilisation to EDF. Thus making the choice of the task layout in memory as important as the choice of scheduling algorithm. This is very relevant for industry, as it is much cheaper and simpler to adjust the task layout through the linker than it is to switch the scheduling algorithm.
Cite as

Will Lunniss, Sebastian Altmeyer, and Robert I. Davis. A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays. In LITES, Volume 1, Issue 1 (2014). Leibniz Transactions on Embedded Systems, Volume 1, Issue 1, pp. 01:1-01:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{lunniss_et_al:LITES-v001-i001-a001,
  author =	{Lunniss, Will and Altmeyer, Sebastian and Davis, Robert I.},
  title =	{{A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:24},
  ISSN =	{2199-2002},
  year =	{2014},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LITES-v001-i001-a001},
  doi =		{10.4230/LITES-v001-i001-a001},
  annote =	{Keywords: Real-time systems, Fixed priority, EDF, Pre-emptive scheduling, Cache related pre-emption delays}
}
Document
DOI: 10.4230/OASIcs.WCET.2010.124
Precomputing Memory Locations for Parametric Allocations

Authors: Jörg Herter and Sebastian Altmeyer

Published in: OASIcs, Volume 15, 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)

Abstract
Current worst-case execution time (WCET) analyses do not support programs using dynamic memory allocation. This is mainly due to the unpredictability of cache performance introduced by standard memory allocators. To overcome this problem, algorithms have been proposed that precompute static allocations for dynamically allocating programs with known numeric bounds on the number and sizes of allocated memory blocks. In this paper, we present a novel algorithm for computing such static allocations that can cope with parametric bounds on the number and sizes of allocated blocks. To demonstrate the usefulness of our approach, we precompute static allocations or a set of existing real-time applications and academic examples.
Cite as

Jörg Herter and Sebastian Altmeyer. Precomputing Memory Locations for Parametric Allocations. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010). Open Access Series in Informatics (OASIcs), Volume 15, pp. 124-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{herter_et_al:OASIcs.WCET.2010.124,
  author =	{Herter, J\"{o}rg and Altmeyer, Sebastian},
  title =	{{Precomputing Memory Locations for Parametric Allocations}},
  booktitle =	{10th International Workshop on Worst-Case Execution Time Analysis (WCET 2010)},
  pages =	{124--135},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-21-7},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{15},
  editor =	{Lisper, Bj\"{o}rn},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2010.124},
  URN =		{urn:nbn:de:0030-drops-28320},
  doi =		{10.4230/OASIcs.WCET.2010.124},
  annote =	{Keywords: WCET analysis, cache analysis, dynamic/static memory allocation}
}
Document
DOI: 10.4230/OASIcs.WCET.2009.2285
Cache-Related Preemption Delay Computation for Set-Associative Caches - Pitfalls and Solutions

Authors: Claire Burguière, Jan Reineke, and Sebastian Altmeyer

Published in: OASIcs, Volume 10, 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) (2009)

Abstract
In preemptive real-time systems, scheduling analyses need - in addition to the worst-case execution time - the context-switch cost. In case of preemption, the preempted and the preempting task may interfere on the cache memory. These interferences lead to additional reloads in the preempted task. The delay due to these reloads is referred to as the cache-related preemption delay (CRPD). The CRPD constitutes a large part of the context-switch cost. In this article, we focus on the computation of upper bounds on the CRPD based on the concepts of useful cache blocks (UCBs) and evicting cache blocks (ECBs). We explain how these concepts can be used to bound the CRPD in case of direct-mapped caches. Then we consider set-associative caches with LRU, FIFO, and PLRU replacement. We show potential pitfalls when using UCBs and ECBs to bound the CRPD in case of LRU and demonstrate that neither UCBs nor ECBs can be used to bound the CRPD in case of FIFO and PLRU. Finally, we sketch a new approach to circumvent these limitations by using the concept of relative competitiveness.
Cite as

Claire Burguière, Jan Reineke, and Sebastian Altmeyer. Cache-Related Preemption Delay Computation for Set-Associative Caches - Pitfalls and Solutions. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09). Open Access Series in Informatics (OASIcs), Volume 10, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{burguiere_et_al:OASIcs.WCET.2009.2285,
  author =	{Burgui\`{e}re, Claire and Reineke, Jan and Altmeyer, Sebastian},
  title =	{{Cache-Related Preemption Delay Computation for Set-Associative Caches - Pitfalls and Solutions}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)},
  pages =	{1--11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Holsti, Niklas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2009.2285},
  URN =		{urn:nbn:de:0030-drops-22856},
  doi =		{10.4230/OASIcs.WCET.2009.2285},
  annote =	{Keywords: WCET analysis, caches, set-associative, preemption, CRPD}
}
Document
DOI: 10.4230/OASIcs.WCET.2008.1664
WCET Analysis for Preemptive Scheduling

Authors: Sebastian Altmeyer and Gernot Gebhard

Published in: OASIcs, Volume 8, 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08) (2008)

Abstract
Hard real-time systems induce strict constraints on the timing of the task set. Validation of these timing constraints is thus a major challenge during the design of such a system. Whereas the derivation of timing guarantees must already be considered complex if tasks are running to completion, it gets even more complex if tasks are scheduled preemptively -- especially due to caches, deployed to improve the average performance. In this paper we propose a new method to compute valid upper bounds on a task's worst case execution time (WCET). Our method approximates an optimal memory layout such that the set of possibly evicted cache-entries during preemption is minimized. This set then delivers information to bound the execution time of tasks under preemption in an adopted WCET analysis.
Cite as

Sebastian Altmeyer and Gernot Gebhard. WCET Analysis for Preemptive Scheduling. In 8th International Workshop on Worst-Case Execution Time Analysis (WCET'08). Open Access Series in Informatics (OASIcs), Volume 8, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{altmeyer_et_al:OASIcs.WCET.2008.1664,
  author =	{Altmeyer, Sebastian and Gebhard, Gernot},
  title =	{{WCET Analysis for Preemptive Scheduling}},
  booktitle =	{8th International Workshop on Worst-Case Execution Time Analysis (WCET'08)},
  pages =	{1--8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-10-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{8},
  editor =	{Kirner, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2008.1664},
  URN =		{urn:nbn:de:0030-drops-16644},
  doi =		{10.4230/OASIcs.WCET.2008.1664},
  annote =	{Keywords: WCET, Preemption}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact